package Algorithm.Sort;

import java.util.Arrays;

public class QuickSortTwo {
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 二路快排
     *
     * @param
     */
    public static void quickSort2(int[] arr) {
        quickSortInternal2(arr, 0, arr.length - 1);
    }

    // 对 arr[l,r]进行快速排序
    private static void quickSortInternal2(int[] arr, int l, int r) {
        // 分区
        if (l > r) {
            return;
        }
        // arr[l,r]上求分区点，arr[l,p]都小于v,arr[p,r]都大于V
        int p = partition2(arr, l, r);
        // 重复上述过程
        quickSortInternal2(arr, l, p - 1);
        quickSortInternal2(arr, p + 1, r);

    }

    // 二路快排的分区
    // 返回arr[l,r]上的分区点
    private static int partition2(int[] arr, int l, int r) {
        int v = arr[l];
        // arr[l + 1..i) <= v
        // [l + 1..l + 1) = 0
        int i = l + 1;
        // arr(j..r] >= v
        // (r...r] = 0
        int j = r;
        while (true) {
            // i从前向后扫描，碰到第一个 >= v的元素停止
            while (i <= j && arr[i] < v) {
                i++;
            }
            // j从后向前扫描，碰到第一个 <= v的元素停止
            while (i <= j && arr[j] > v) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
            return j;
        }
        // j落在最后一个 <= v的元素身上
        swap(arr, l, j);
        return j;
    }

    public static void main(String[] args) {
        int[] arr2 = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        quickSort2(arr2);
        System.out.println(Arrays.toString(arr2));
    }
}
